package main

import (
	"fmt"
	"math/rand"
	"time"
)

func main() {
	rand.Seed(time.Now().UnixNano())
	n := 10
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		arr[i] = rand.Intn(100)
	}

	fmt.Println("--- 排序前 ---")
	fmt.Println(arr)

	fmt.Println("--- 排序后 ---")
	heapSort(arr)
	fmt.Println(arr)
}

// heapSort 堆排序
func heapSort(arr []int) {
	size := len(arr)
	buildMaxHeap(arr, size)

	for i := size - 1; i > 0; i-- {
		arr[0], arr[i] = arr[i], arr[0]
		size--
		maxHeapify(arr, 0, size)
	}
}

// buildMaxHeap 构造大顶堆
func buildMaxHeap(arr []int, size int) {
	for i := size / 2; i >= 0; i-- {
		maxHeapify(arr, i, size)
	}
}

// maxHeapify 对大顶堆的某个结点进行堆化
func maxHeapify(arr []int, i, size int) {
	l, r, largest := i*2+1, i*2+2, i

	if l < size && arr[l] > arr[largest] {
		largest = l
	}
	if r < size && arr[r] > arr[largest] {
		largest = r
	}

	if largest != i {
		arr[i], arr[largest] = arr[largest], arr[i]
		maxHeapify(arr, largest, size)
	}
}
